D - Minimum Triangulation (区间DP,结论题)
思路
一眼看出结论，但是实际上它是个区间DP题，枚举区间$l-r$中的一个点$k$ 然后继续做一个三角形
E - Palindrome-less Arrays (DP)
思路
首先没有大于1的奇数的回文那就是没有长度为3的回文，可以发现只要没有长度为3的回文那就肯定不会有大于长度为3的奇数回文 所以我们就可以把问题拆成奇数和偶数的两个串 要求任意相邻两个不相同的个数
首先如果不是-1答案就已经固定了,如果是-1就考虑这种-1的长度的情况
$1.$如果全部都是-1例如$xxxxx$ 那么我们就直接得到这种有$k*pow(k-1,n-1)$
$2.$如果是$axxxx$或者$xxxxa$那么我们就可以直接得到$pow(k-1,n)$
$3.$如果是$axxxa$ 那么假设答案就是$dp[len][1]$
$4.$如果是$axxxxb$ 那么假设就是$dp[len][0]$
首先定义$dp[len][0]$ 为长度为$len$的以上$3/4$情况
明显的如果$len=1$那么$dp[len][1]=k-1$ and $dp[len][0]=k-2$
现在考虑$dp[len+1][1]$ 就相当于现在已经有了一个$axxxxa$
对于第一个$x$ 它肯定不是$a$ 那么他就可能是$k$中除了$a$之外的$k-1$个,所以假设它是$b$
那么现在就是$axxxb$ 发现这个答案我们之前是不是求过了是不是就是$dp[len][0]$ 啊
然后$b$有$k-1$中情况所以$dp[len][1]=(k-1)*dp[len-1][0]$
另一种同理